package com.chenken;

/**
 *  二分查找
 * @author ken.chen
 *
 */
public class BinarySearch {

	public static void main(String[] args) {
		int[] numArray = {1,2,10,20,21,23,24,30,50,80,100};
		System.out.println(binarySearch(numArray,30));
		System.out.println(binarySearch02(numArray,11));
	}
	
	/**
	 * 找出数字在数组中的下标
	 * 数组是从小到大的有序数组
	 * @param array
	 * @param num
	 * @return
	 */
	public static int binarySearch(int[] array,int num) {
		int begin = 0,end = array.length;
		while(begin < end) {
			int middle = (end + begin) >> 1;
			if(array[middle] > num) {
				end = middle;
			}else if(array[middle] < num) {
				begin = middle+1;
			}else {
				return middle;
			}
		}
		return -1;
	}
	
	/**
	 * 找出数字在数组中待插入下标
	 * 数组是从小到大的有序数组
	 * @param array
	 * @param num
	 * @return
	 */
	public static int binarySearch02(int[] array,int num) {
		int begin = 0,end = array.length;
		while(begin < end) {
			int middle = (end + begin) >> 1;
			if(array[middle] > num) {
				end = middle;
			}else if(array[middle] < num) {
				begin = middle+1;
			}
		}
		return begin;
	}
}
